/**
 * 52. N皇后 II
 * https://leetcode-cn.com/problems/n-queens-ii/
 */
public class Solutions_52 {
    public static void main(String[] args) {
//        int n = 4;  // output: 2
//        int n = 5;  // output: 10
        int n = 8;  // output: 92

        int result = totalNQueens(n);
        System.out.println(result);
    }

    private static int res = 0;
    private static int queenCount = 0;
    private static boolean[] colunm = null;
    private static boolean[] mainDiagonal = null;
    private static boolean[] secondDiagonal = null;

    public static int totalNQueens(int n) {
        queenCount = n;
        // 使用哈希映射数组来代替 Set
        // 在棋盘中，每个坐标都是唯一的
        colunm = new boolean[n];
        // 行列之差相同，说明两坐标在同一主斜线上
        mainDiagonal = new boolean[2 * n];
        // 行列之和相同，说明两坐标在同一副斜线上
        secondDiagonal = new boolean[2 * n];
        backtrack(0);
        return res;
    }

    public static void backtrack(int row) {
        if (row == queenCount) {
            res ++;
            return;
        }
        for (int i = 0; i < queenCount; i++) {
            // 列，主斜线，副斜线上都存在“皇后”
            if (colunm[i] || mainDiagonal[row - i + queenCount] || secondDiagonal[row + i]) {
                continue;
            }
            // 标记为“皇后”
            colunm[i] = mainDiagonal[row - i + queenCount] = secondDiagonal[row + i] = true;
            // 递归，计算下一行“皇后”的位置
            backtrack(row + 1);
            // 还原状态为未标记
            colunm[i] = mainDiagonal[row - i + queenCount] = secondDiagonal[row + i] = false;
        }
    }
}
